/**
 * Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path 
from the root node down to the farthest leaf node.
 */
package com.xinpan.exercise;

public class MaxBinaryTreeDepth {
    public int maxDepth(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root == null)
            return 0;
            
        int ldepth = subDepth(root.left, 1);
        int rdepth = subDepth(root.right, 1);
        
        return ldepth > rdepth ? ldepth : rdepth;
    }
    
    int subDepth(TreeNode root, int depth)
    {
        if(root == null)
            return depth;
            
        int ldepth = subDepth(root.left, depth+1);
        int rdepth = subDepth(root.right, depth+1);
        
        return ldepth > rdepth ? ldepth : rdepth;
    }
}
